/**
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
 * 搜索旋转排序数组
 * @param nums 
 * @param target 
 * @returns 
 */
const search = (nums: number[], target: number): number => { 
     // 二分 O(logn)
    // [8, 9, 1, 2, 3, 4, 5] 8

    const len = nums.length;
    let s = 0,
        e = len;

    while (s < e) {
        // 获取中间位置的元素
        const m = (s + e) >> 1

        // 如果找到了, 返回该位置的索引
        if (nums[m] === target) return m

        // 首项小于等于中间元素
        if (nums[0] <= nums[m]) {
            if (nums[0] <= target && target < nums[m]) {
                // 往前找
                e = m
            } else {
                // 往后找
                s = m + 1
            }
        } else {
            // 首项大于中间元素
            if (nums[m] < target && target <= nums[len - 1]) {
                // 往后找
                s = m + 1;
            } else {
                // 往前找
                e = m
            }
        }
    }
    return -1
};

// 常规遍历 O(n)
const search2 = (nums: number[], target: number): number => {
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        if (nums[i] === target) return i
    }
    return -1
};

// const binarySearch = (nums: number[], target: number) => {
//     let s = 0,
//         e = nums.length - 1;

//     while (s < e) {
//         const m = (s + e) >> 1

//         if (nums[m] === target) return m
//         else if (nums[m] < target) {
//             // 往后找
//             s = m + 1
//         } else {
//             // 往前找
//             e = m
//         }
//     }
//     return -1
// }

// const nums = [1, 2, 3, 4, 5, 6]
// console.log(binarySearch(nums, 3))
// console.log(binarySearch(nums, 1))
// console.log(binarySearch(nums, 2))
// console.log(binarySearch(nums, 4))
// console.log(binarySearch(nums, 5))
// console.log(binarySearch(nums, 6))
// console.log(binarySearch(nums, 8))